package com.mamingchao.issue.UnionFindSet;

/**
 * 并查集 就是每个集合都定义一个 代表node， flag node；不同的node，判断是否属于同一个集合，就判断 node的flag node是不是一个
 * 然后 在一个集合里，每个node找到自己flag node的时间复杂度，都是 O(1)
 *
 * 并查集 提供两个基本功能 1： isSameSet(Node node1, Node node2) 2:Union()
 * Created by mamingchao on 2022/9/3.
 */
public class UnionFindSet {

    class Node {
        int value;
        // 父节点链表指针
        Node parent = this;

        // 如果该节点是flag node，表示该集合，最长的多叉树深度
        int depthOfTree = 0;
    }


    /**
     * 判断两个node是不是同一个结合
     * 每个node都有一个代表；代表就是node一直向上找，且父节点不是自己的
     * @param node1
     * @param node2
     * @return
     */
    public boolean isSameSet(Node node1, Node node2) {

        Node flagNode1 = this.findFlagNode(node1);
        Node flagNode2 = this.findFlagNode(node2);

        return flagNode1 == flagNode2;
    }

    /**
     * 这里面可以做一个优化，即每次向上查找FlagNode的时候，都把节点直接挂在 FlagNode上
     * 这样如果调用 findFlagNode 方法足够频繁的话，能保证一个集合里，大部分或者所有node
     * 都扁平化的直接挂在 FlagNode上；有结论说，当findFlagNode 调用次数 > 集合成员数N的话，
     * 并查集的判断是否是同一个结合&集合合并的时间复杂度就变成O(1)
     * 这样判断是不是一个集合和做 集合合并的时候，时间复杂度会大大下降
     *
     * 另外一个好处就是，集合合并时候，判断是A集合挂在B的FlagNode上，还是反过来，
     * 就可以直接判断 那个集合的成员多，而不用判断 多叉树的深度了
     * @param node
     * @return
     */
    private Node findFlagNode(Node node) {
        if (node == null) {
            return null;
        }

        Node curNode = node;
        // 一直向上找 flag node
        while (curNode.parent !=null && curNode.parent != curNode) {
            curNode = node.parent;
        }

        return curNode;
    }

    /**
     * 两个节点所在的集合，合并
     * 合并过程中，应坚守
     * @param node1
     * @param node2
     */
    private void union(Node node1, Node node2){

        if (isSameSet(node1, node2)) {
            return;
        }

        Node flagNode1 = this.findFlagNode(node1);
        Node flagNode2 = this.findFlagNode(node2);

        // 多叉树深度短的，往多叉树深度深的上面挂
        if (flagNode1.depthOfTree >= flagNode2.depthOfTree) {
            flagNode2.parent = flagNode1;
        } else {
            flagNode1.parent = flagNode2;
        }
    }
}
